<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>冒泡排序</title>
</head>

<body>
    <script>
        //时间复杂度 O（n^2），改进后最优时间复杂度O（n）
        // 假设要升序列表
        // 列表相邻的两个数比较，如果前面的数比后面大，则交换这两个数，在该过程中找出最大的数，并冒到最上面
        // 一趟排序完成后则无序区减一个数，有序区加一个数
        function bubbleSort(unordArr) {
            let p = 0;
            for (let i = 0; i < unordArr.length; i++) {
                //i为有序区的长度，最后无序区只剩一个数字，不需要比较
                console.log("%");
                for (let j = 0; j < unordArr.length - i - 1; j++) {
                    //此处j是bubble位置，只能到无序区的倒数第二个位置
                    let bubble = unordArr[j];
                    let nextnum = unordArr[j + 1];
                    unordArr[j] = Math.min(bubble, nextnum);
                    unordArr[j + 1] = Math.max(bubble, nextnum); //降序排列的话将这两个赋值语句调换
                    // p是检测无序区的序列是否都符合顺序
                    if (bubble === unordArr[j]) { //当遇到更大的bubble时
                        p++;
                        console.log(p);
                        console.log(unordArr.length - i - 1);
                        if (p === unordArr.length - i - 1) {
                            //当p的值等于无序区长度减一（bubble只能也只需检测到这个位置），
                            console.log(unordArr); //其中刚排好序时那一次的bubble是必定变化的，所以需要一次循环捕获bubble不变
                            return 1; //此时说明无序区已经有序直接结束循环
                        }
                    } else {
                        //当bubble正常向上冒时，要将监测数据p值归零
                        p = 0;
                    }
                }
                console.log(unordArr);
            }
            console.log(unordArr);
        }
        bubbleSort([7, 1, 2, 2, 3, 3, 4, 5]);
    </script>
</body>

</html>